{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Surface Area of 3D Shapes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #math #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #数学 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: surfaceArea"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #三维形体的表面积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>n * n</code> 的网格&nbsp;<code>grid</code> ，上面放置着一些&nbsp;<code>1 x 1 x 1</code>&nbsp;的正方体。每个值&nbsp;<code>v = grid[i][j]</code>&nbsp;表示&nbsp;<code>v</code>&nbsp;个正方体叠放在对应单元格&nbsp;<code>(i, j)</code>&nbsp;上。</p>\n",
    "\n",
    "<p>放置好正方体后，任何直接相邻的正方体都会互相粘在一起，形成一些不规则的三维形体。</p>\n",
    "\n",
    "<p>请你返回最终这些形体的总表面积。</p>\n",
    "\n",
    "<p><strong>注意：</strong>每个形体的底面也需要计入表面积中。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/08/tmp-grid2.jpg\" style=\"height: 80px; width: 80px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,2],[3,4]]\n",
    "<strong>输出：</strong>34\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/08/tmp-grid4.jpg\" style=\"height: 100px; width: 100px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,1,1],[1,0,1],[1,1,1]]\n",
    "<strong>输出：</strong>32\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/08/tmp-grid5.jpg\" style=\"height: 100px; width: 100px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[2,2,2],[2,1,2],[2,2,2]]\n",
    "<strong>输出：</strong>46\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 50</code></li>\n",
    "\t<li><code>0 &lt;= grid[i][j] &lt;= 50</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [surface-area-of-3d-shapes](https://leetcode.cn/problems/surface-area-of-3d-shapes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [surface-area-of-3d-shapes](https://leetcode.cn/problems/surface-area-of-3d-shapes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[3,4]]', '[[1,1,1],[1,0,1],[1,1,1]]', '[[2,2,2],[2,1,2],[2,2,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        N = len(grid)\n",
    "\n",
    "        ans = 0\n",
    "        for r in range(N):\n",
    "            for c in range(N):\n",
    "                if grid[r][c]:\n",
    "                    ans += 2\n",
    "                    for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
    "                        if 0 <= nr < N and 0 <= nc < N:\n",
    "                            nval = grid[nr][nc]\n",
    "                        else:\n",
    "                            nval = 0\n",
    "\n",
    "                        ans += max(grid[r][c] - nval, 0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid)):\n",
    "               cur = grid[i][j]\n",
    "               if cur > 0:\n",
    "                   res += cur * 4 + 2\n",
    "                   res -= min(cur, grid[i-1][j]) * 2 if i > 0 else 0\n",
    "                   res -= min(cur, grid[i][j-1]) * 2 if j > 0 else 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        origin = neighbor = cur = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                origin += grid[i][j]\n",
    "                cur += grid[i][j] - 1 if grid[i][j] > 1 else 0\n",
    "                if j < n-1:\n",
    "                    neighbor += min(grid[i][j], grid[i][j+1])\n",
    "                if i < m-1:\n",
    "                    neighbor += min(grid[i][j], grid[i+1][j])\n",
    "        return 6*origin - 2*(cur+neighbor)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid)):\n",
    "               cur = grid[i][j]\n",
    "               if cur > 0:\n",
    "                   res += (cur << 2) + 2\n",
    "                   res -= min(cur, grid[i-1][j]) << 1 if i > 0 else 0\n",
    "                   res -= min(cur, grid[i][j-1]) << 1 if j > 0 else 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        N = len(grid)\n",
    "        ans = 0\n",
    "        for r in range(N):\n",
    "            for c in range(N):\n",
    "                if grid[r][c]:\n",
    "                    ans+=2\n",
    "                    for nr,nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):\n",
    "                        if 0<=nr<N and 0<=nc<N:\n",
    "                            neigh = grid[nr][nc]\n",
    "                        else:\n",
    "                            neigh = 0\n",
    "                        ans += max(grid[r][c]-neigh, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        n = len(grid)\n",
    "        for r in range(n):\n",
    "            for c in range(n):\n",
    "                x = grid[r][c]\n",
    "                a = x * 6 - (x - 1) * 2  if x != 0 else 0\n",
    "                if c + 1 < n:\n",
    "                    a -= min(x, grid[r][c + 1]) * 2\n",
    "                if r + 1 < n:\n",
    "                    a -= min(x, grid[r + 1][c]) * 2\n",
    "                ans += a\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0:\n",
    "                    res += grid[i][j]\n",
    "                if i == m - 1:\n",
    "                    res += grid[i][j]\n",
    "                if j == 0:\n",
    "                    res += grid[i][j]\n",
    "                if j == n - 1:\n",
    "                    res += grid[i][j]\n",
    "                if grid[i][j] != 0:\n",
    "                    res += 2\n",
    "                if i < m - 1:\n",
    "                    res += abs(grid[i][j] -  grid[i + 1][j])\n",
    "                if j < n - 1:\n",
    "                    res += abs(grid[i][j] - grid[i][j + 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        h=len(grid)\n",
    "        w=len(grid[0])\n",
    "        result=sum([sum([1 for x in y if x>0]) for y in grid])*2\n",
    "        result+=sum([grid[y][0] for y in range(h)])+sum([grid[y][w-1] for y in range(h)])\n",
    "        result+=sum([grid[0][x] for x in range(w)])+sum([grid[h-1][x] for x in range(w)])\n",
    "        result+=sum([sum([abs(grid[y][x]-grid[y][x+1]) for x in range(w-1)]) for y in range(h)])\n",
    "        result+=sum([sum([abs(grid[y][x]-grid[y+1][x]) for y in range(h-1)]) for x in range(w)])\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] > 0:\n",
    "                    ans += grid[i][j] * 4 + 2\n",
    "                if i > 0:\n",
    "                    ans -= 2 * min(grid[i][j], grid[i - 1][j])\n",
    "                if j > 0:\n",
    "                    ans -= 2 * min(grid[i][j], grid[i][j - 1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n,m = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]>0:\n",
    "                    ans += grid[i][j]*4 + 2\n",
    "                if i>0:\n",
    "                    ans -= min(grid[i][j],grid[i-1][j])*2\n",
    "                if j > 0:\n",
    "                    ans -= min(grid[i][j],grid[i][j-1])*2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        s=0\n",
    "        for i in grid:\n",
    "            for j in i:\n",
    "                if j>0:\n",
    "                    s+=(4*j+2)\n",
    "        direction=[[1,0],[-1,0],[0,1],[0,-1]]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                for direct in direction:\n",
    "                    if -1<i+direct[0]<len(grid) and -1<j+direct[1]<len(grid[0]):\n",
    "                        s-=min(grid[i][j],grid[i+direct[0]][j+direct[1]])\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        if grid == None or len(grid) < 1 or len(grid[0]) < 1: return 0\n",
    "        blocks, coverd = 0, 0\n",
    "        n, m= len(grid), len(grid[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                blocks += grid[i][j]\n",
    "                if grid[i][j] > 1:\n",
    "                    # 列内部遮盖\n",
    "                    coverd += grid[i][j] - 1\n",
    "                if i > 0:\n",
    "                    # 上一行同一列遮盖\n",
    "                    coverd += min(grid[i - 1][j], grid[i][j])\n",
    "                if j > 0:\n",
    "                    # 同一行上一列遮盖\n",
    "                    coverd += min(grid[i][j - 1], grid[i][j])\n",
    "        return blocks * 6 - coverd * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        ans = sum(sum(grid, [])) * 6\n",
    "        getMid = lambda n: 2*(n-1)\n",
    "        def getVal(i, j, grid):\n",
    "            w, h = len(grid[0]), len(grid)\n",
    "            if i < 0 or i >= h or j < 0 or j >= w:\n",
    "                return 0\n",
    "            return grid[i][j]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if not grid[i][j]:\n",
    "                    continue\n",
    "                ans -= getMid(grid[i][j])\n",
    "                ans -= min(grid[i][j], getVal(i-1, j, grid))\n",
    "                ans -= min(grid[i][j], getVal(i+1, j, grid))\n",
    "                ans -= min(grid[i][j], getVal(i, j-1, grid))\n",
    "                ans -= min(grid[i][j], getVal(i, j+1, grid))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        search = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0: continue\n",
    "                cur = 4*grid[i][j] + 2 \n",
    "                for k in range(4):\n",
    "                    di, dj = i+search[k][0], j+search[k][1]\n",
    "                    if di >= 0 and di < n and dj >=0 and dj < n:\n",
    "                        cur -= min(grid[di][dj], grid[i][j])\n",
    "                total += cur\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\r\n",
    "        res=0\r\n",
    "        r=[0]*len(grid[0])\r\n",
    "        l=[0]*len(grid)\r\n",
    "        for i in range(len(grid)):\r\n",
    "            for j in range(len(grid[0])):\r\n",
    "                if grid[i][j]>0:\r\n",
    "                    res+=2\r\n",
    "                res+=abs(grid[i][j]-r[j])\r\n",
    "                res+=abs(grid[i][j]-l[i])\r\n",
    "                r[j]=grid[i][j]\r\n",
    "                l[i]=grid[i][j]\r\n",
    "                    \r\n",
    "        return res+sum(r)+sum(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        a = 0\n",
    "        # 计算大于0的个数 计算上下底面积\n",
    "        ans = 0\n",
    "        # 计算侧面积\n",
    "        n = len(grid)\n",
    "        for i in range(n):\n",
    "            row = 0\n",
    "            lie = 0\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "                    a = a + 1\n",
    "                ans = ans + abs(row - grid[i][j]) + abs(lie - grid[j][i])\n",
    "                lie = grid[j][i]\n",
    "                row = grid[i][j]\n",
    "            ans = ans + row + lie\n",
    "        return ans + a * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        s=len(grid)\n",
    "        for i in range(s):\n",
    "            for j in range(s):\n",
    "                t=grid[i][j]\n",
    "                #四个边，加上上底和下底\n",
    "                if grid[i][j]!=0:\n",
    "                    ans+= t+t+1\n",
    "                #减去行间重叠部分\n",
    "                if i>0:\n",
    "                    ans -= min(t,grid[i-1][j])\n",
    "                #减去列间重叠部分\n",
    "                if j>0:\n",
    "                    ans -= min(t,grid[i][j-1])\n",
    "        return ans<<1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        N = len(grid)\n",
    "        ans = 0\n",
    "        for r in range(N):\n",
    "            for c in range(N):\n",
    "                if grid[r][c]:\n",
    "                    ans += 2\n",
    "                    for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
    "                        if 0 <= nr < N and 0 <= nc < N:\n",
    "                            nval = grid[nr][nc]\n",
    "                        else:\n",
    "                            nval = 0\n",
    "\n",
    "                        ans += max(grid[r][c] - nval, 0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    ans += 2\n",
    "                    for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):\n",
    "                        if 0 <= x < n and 0 <= y < n:\n",
    "                            v = grid[x][y]\n",
    "                        else:\n",
    "                            v = 0\n",
    "                        ans += max(grid[i][j] - v, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        N = len(grid)\n",
    "\n",
    "        ans = 0\n",
    "        for r in range(N):\n",
    "            for c in range(N):\n",
    "                \n",
    "                if grid[r][c]:\n",
    "                    # 上下\n",
    "                    ans += 2\n",
    "                    # 前后左右，如果有值，这该面高度减去相邻的高度，\n",
    "                    for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
    "                        if 0 <= nr < N and 0 <= nc < N:\n",
    "                            nval = grid[nr][nc]\n",
    "                        else:\n",
    "                            nval = 0\n",
    "\n",
    "                        ans += max(grid[r][c] - nval, 0)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                high = grid[i][j]\n",
    "                if high > 0:\n",
    "                    ans += 2    # 上下表面\n",
    "                    for i2, j2 in (i + 1, j), (i - 1, j), (i, j + 1), (i, j + 1):\n",
    "                        if -1 < i2 < n and -1 < j2 < n:\n",
    "                            if grid[i2][j2] < high:\n",
    "                                ans += high - grid[i2][j2]\n",
    "                        else:\n",
    "                            ans += high\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        cube_nums = sum(sum(row) for row in grid)\n",
    "        hide_nums = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] > 0:\n",
    "                    hide_nums += grid[i][j] - 1\n",
    "                if i > 0:\n",
    "                    hide_nums += min(grid[i-1][j], grid[i][j])\n",
    "                if j > 0:\n",
    "                    hide_nums += min(grid[i][j-1], grid[i][j])\n",
    "        return 6*cube_nums - 2*hide_nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        S=0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>0:\n",
    "                    S+=grid[i][j]*1*1*6-(grid[i][j]-1)*2\n",
    "                if i>0:\n",
    "                    S-=min(grid[i][j],grid[i-1][j])*2\n",
    "                if j>0:\n",
    "                    S-=min(grid[i][j],grid[i][j-1])*2\n",
    "        return S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid[0])\n",
    "        box_all=0\n",
    "        sub_all=0\n",
    "        sub_xy=0\n",
    "        z_sub=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                pos=grid[i][j]\n",
    "                if i<n-1 and j<n-1:\n",
    "                    x_sub=2*min(pos,grid[i][j+1])\n",
    "                    y_sub=2*min(pos,grid[i+1][j])\n",
    "                    sub_xy=sub_xy+x_sub+y_sub\n",
    "                if i==n-1 and j!=n-1:\n",
    "                    sub_xy+=2*min(pos,grid[i][j+1])\n",
    "                if j==n-1 and i!=n-1:\n",
    "                    sub_xy+=2*min(pos,grid[i+1][j])\n",
    "                box_all=pos+box_all\n",
    "                z_sub+=2*(pos-1) if pos>0 else 0\n",
    "        result=6*box_all-sub_xy-z_sub\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        m, n, ans = len(grid), len(grid[0]), 0\n",
    "        drcs = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if grid[r][c] > 0: ans += 2\n",
    "                for dr, dc in drcs:\n",
    "                    nr, nc, tmp = r + dr, c + dc, 0\n",
    "                    if -1 < nr < m and -1 < nc < n:\n",
    "                        ans += max(0, grid[r][c] - grid[nr][nc])\n",
    "                    else: ans += grid[r][c]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        cube_nums = sum(sum(row) for row in grid)\n",
    "        hide_nums = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid)):\n",
    "                if grid[i][j] > 0:\n",
    "                    hide_nums += grid[i][j] - 1\n",
    "                if i > 0:\n",
    "                    hide_nums += min(grid[i-1][j], grid[i][j])\n",
    "                if j > 0:\n",
    "                    hide_nums += min(grid[i][j-1], grid[i][j])\n",
    "        return 6*cube_nums - 2*hide_nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        def b(a,b,c,d,e):\n",
    "            if a==0:return 0\n",
    "            ans=2\n",
    "            la=[b,c,d,e]\n",
    "            for i in la:\n",
    "                if i<a:ans+=a-i\n",
    "            return ans\n",
    "        k=len(grid)\n",
    "        grid=[[0]*k]+grid+[[0]*k]\n",
    "        for i in range(k+2):grid[i]=[0]+grid[i]+[0]\n",
    "        for i in range(1,k+1):\n",
    "            for j in range(1,k+1):\n",
    "                ans+=b(grid[i][j],grid[i+1][j],grid[i-1][j],grid[i][j+1],grid[i][j-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        ans = 0\n",
    "        \n",
    "        def get(i, j):\n",
    "            if i < 0 or j < 0 or j >=n or i >= n:\n",
    "                return 0\n",
    "            return grid[i][j]\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ## 没有立方体不需要处理\n",
    "                if grid[i][j] == 0: continue\n",
    "                ## 1个立方体有6个面, 再减去自身堆叠中产生的重复面\n",
    "                ans = ans + grid[i][j] * 6 - (grid[i][j] - 1) * 2\n",
    "                ## 和4个方向相邻产生的重复面\n",
    "                for x, y in ((1, 0), (-1, 0), (0, 1), (0, -1)):\n",
    "                    ans -= min(grid[i][j], get(i+x, j+y))\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        N = len(grid)\n",
    "\n",
    "        ans = 0\n",
    "        for r in range(N):\n",
    "            for c in range(N):\n",
    "                if grid[r][c]:\n",
    "                    ans += 2\n",
    "                    for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
    "                        if 0 <= nr < N and 0 <= nc < N:\n",
    "                            nval = grid[nr][nc]\n",
    "                        else:\n",
    "                            nval = 0\n",
    "\n",
    "                        ans += max(grid[r][c] - nval, 0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        i,j,n=0,0,len(grid)\n",
    "        while(i<n):\n",
    "            while(j<n):\n",
    "                if(grid[i][j]>0):\n",
    "                    ans=ans+2+4*grid[i][j]\n",
    "                if(i==0 and j>0):\n",
    "                    ans=ans-2*min(grid[i][j],grid[i][j-1])\n",
    "                if(j==0 and i>0):\n",
    "                    ans=ans-2*min(grid[i][j],grid[i-1][j])\n",
    "                if(i>0 and j>0):\n",
    "                    ans=ans-2*min(grid[i][j],grid[i-1][j])-2*min(grid[i][j],grid[i][j-1])\n",
    "                j=j+1\n",
    "            i=i+1\n",
    "            j=0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\r\n",
    "        R,C=len(grid),len(grid[0])\r\n",
    "        ret=0\r\n",
    "        row_heights=[0]*R\r\n",
    "        col_heights=[0]*C\r\n",
    "        for r in range(R):\r\n",
    "            for c in range(C):\r\n",
    "                if grid[r][c]==0:\r\n",
    "                    continue\r\n",
    "                ret+=2\r\n",
    "                dirs=[-1,0,1,0,-1]\r\n",
    "                for i in range(4):\r\n",
    "                    nr,nc=r+dirs[i],c+dirs[i+1]\r\n",
    "                    if 0<=nr<R and 0<=nc<C:\r\n",
    "                        ret+=max(0,grid[r][c]-grid[nr][nc])\r\n",
    "                    else:\r\n",
    "                        ret+=grid[r][c]\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        h=len(grid)\n",
    "        w=len(grid[0])\n",
    "        result=sum([sum([1 for x in y if x>0]) for y in grid])*2\n",
    "        result+=sum([grid[y][0] for y in range(h)])+sum([grid[y][w-1] for y in range(h)])\n",
    "        result+=sum([grid[0][x] for x in range(w)])+sum([grid[h-1][x] for x in range(w)])\n",
    "        result+=sum([sum([abs(grid[y][x]-grid[y][x+1]) for x in range(w-1)]) for y in range(h)])\n",
    "        result+=sum([sum([abs(grid[y][x]-grid[y+1][x]) for y in range(h-1)]) for x in range(w)])\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\r\n",
    "        res=0\r\n",
    "        for i in range(len(grid)):\r\n",
    "            last=0\r\n",
    "            \r\n",
    "            for j in range(len(grid[0])):\r\n",
    "                if grid[i][j]>0:\r\n",
    "                    res+=2\r\n",
    "                res+=abs(grid[i][j]-last)\r\n",
    "                last=grid[i][j]\r\n",
    "            res+=last\r\n",
    "            print(res)\r\n",
    "        for j in range(len(grid[0])):\r\n",
    "            last=0\r\n",
    "            for i in range(len(grid)):\r\n",
    "                res+=abs(grid[i][j]-last)\r\n",
    "                last=grid[i][j]\r\n",
    "            res+=last\r\n",
    "                    \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        ans=0\n",
    "        for r in range(n):\n",
    "            for c in range(n):\n",
    "                if grid[r][c]:\n",
    "                    ans+=2\n",
    "                    for nr,nc in ((r-1,c),(r+1,c),(r,c+1),(r,c-1)):\n",
    "                        if 0<=nr<n and 0<=nc<n:\n",
    "                            nval=grid[nr][nc]\n",
    "                        else:\n",
    "                            nval=0\n",
    "                        ans+=max(grid[r][c]-nval,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        cubes, faces = 0, 0\n",
    "        n = len(grid)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                cubes += grid[i][j]\n",
    "                if grid[i][j] > 0:\n",
    "                    faces += grid[i][j] - 1\n",
    "\n",
    "                if i > 0:\n",
    "                    faces += min(grid[i - 1][j], grid[i][j])\n",
    "                if j > 0:\n",
    "                    faces += min(grid[i][j - 1], grid[i][j])\n",
    "        return 6 * cubes - 2 * faces"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(v):\n",
    "    return sum(max(0, a - b) + max(0, a - c) for a, b, c in zip(v, [0] + v[:-1], v[1:] + [0]))\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        return 2 * sum(sum(g > 0 for g in row) for row in grid) + \\\n",
    "                sum(f(row) for row in grid) + \\\n",
    "                sum(f([grid[i][j] for i in range(len(grid))]) for j in range(len(grid[0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        N = len(grid)\n",
    "\n",
    "        ans = 0\n",
    "        for r in range(N):\n",
    "            for c in range(N):\n",
    "                if grid[r][c]:\n",
    "                    ans += 2\n",
    "                    for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
    "                        if 0 <= nr < N and 0 <= nc < N:\n",
    "                            nval = grid[nr][nc]\n",
    "                        else:\n",
    "                            nval = 0\n",
    "\n",
    "                        ans += max(grid[r][c] - nval, 0)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        l = len(grid)\n",
    "        w = len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(l):\n",
    "            for j in range(w):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                res = 0\n",
    "                for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                        x = i + dx\n",
    "                        y = j + dy\n",
    "                        if x < 0 or x >= l or y < 0 or y >= w or grid[x][y] == 0:\n",
    "                            res += grid[i][j]\n",
    "                        else:\n",
    "                            res += max(grid[i][j] - grid[x][y], 0)\n",
    "                res += 2\n",
    "                ans += res\n",
    "        return ans\n",
    "            \n",
    "\n",
    "                \n",
    "\n",
    "        \n",
    "\n",
    "# 8 + 8 + 6 + 4 + 4 + 4\n",
    "# 6 + 7 + 6 + 7 + 4 + 4\n",
    "# (1 + 1 + 1 + 1) + (1 + 2 + 2 + 1 + 1) + (1 + 2 + 4 + 4 + 1 + 1) + (3 + 2 + 3 + 1 + 1)\n",
    "# 4 + 7 + 13 + 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        def helper(x, y):\n",
    "            if x < 0 or x >= n or y < 0 or y >= m:\n",
    "                return 0\n",
    "            return grid[x][y]\n",
    "        ans = 0\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                v = grid[i][j]\n",
    "                if v == 0:\n",
    "                    continue\n",
    "                ans += 6 * v - (v - 1) * 2\n",
    "                for di in dirs:\n",
    "                    nx, ny = i + di[0], j + di[1]\n",
    "                    ans -= min(v, helper(nx, ny))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        cube_num = sum(sum(row) for row in grid)\n",
    "        hide_num = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                # 俯视\n",
    "                # 前后两面的重叠个数 grid[i][j] - 1\n",
    "                if grid[i][j] > 0:\n",
    "                    hide_num += grid[i][j] - 1\n",
    "                # 左右两面的重叠个数 min(grid[i-1][j], grid[i][j]) -- 两个位置的“高”相交（即最小值）\n",
    "                if i > 0:\n",
    "                    hide_num += min(grid[i - 1][j], grid[i][j])\n",
    "                # 上下两面的重叠个数 min(grid[i][j-1], grid[i][j]) -- 两个位置的“长”相交（即最小值）\n",
    "                if j > 0:\n",
    "                    hide_num += min(grid[i][j - 1], grid[i][j])\n",
    "        #\n",
    "        return cube_num * 6 - hide_num * 2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>0:\n",
    "                    res+=grid[i][j]*4+2\n",
    "                if i>0:\n",
    "                    res-=min(grid[i][j],grid[i-1][j])*2\n",
    "                if j>0:\n",
    "                    res-=min(grid[i][j],grid[i][j-1])*2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        minus = 0\n",
    "        num = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid)):\n",
    "                num += grid[i][j]\n",
    "                if grid[i][j] >= 2:\n",
    "                    minus += (grid[i][j] - 1) * 2\n",
    "                if i != len(grid) - 1:\n",
    "                    minus +=  min(grid[i][j], grid[i+1][j]) * 2\n",
    "                if j != len(grid) -1:\n",
    "                    minus +=  min(grid[i][j], grid[i][j+1]) * 2\n",
    "        \n",
    "    \n",
    "        return num * 6 - minus"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        N = len(grid)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "\n",
    "        for r in range(N):\n",
    "            for c in range(N):\n",
    "                if grid[r][c]:\n",
    "                    res += 2\n",
    "                    for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
    "\n",
    "                        if 0 <= nr < N and 0 <= nc < N:\n",
    "                            nval = grid[nr][nc]\n",
    "                        else:\n",
    "                            nval = 0\n",
    "                        \n",
    "                        res += max(grid[r][c] - nval, 0)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        top = 0\n",
    "        out = sum(grid[0][i] + grid[i][0] + grid[-1][i] + grid[i][-1] for i in range(n))\n",
    "        diff = 0\n",
    "        direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:  top += 1\n",
    "                for dx, dy in direction:\n",
    "                    X, Y = i + dx, j + dy\n",
    "                    if 0 <= X < n and 0 <= Y < n:\n",
    "                        diff += abs(grid[i][j] - grid[X][Y])\n",
    "        \n",
    "        return top * 2 + diff // 2 + out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        a,b,c,d=0,0,0,0\n",
    "        for i in grid:\n",
    "            for j in range(len(i)):\n",
    "                a+=i[j]\n",
    "                b=max(b,b+i[j]-1)\n",
    "                if j+1<len(i) and i[j]>0 and i[j+1]>0:\n",
    "                    c+=min(i[j],i[j+1])\n",
    "        m=list([i for i in zip(*grid)])\n",
    "        for i in m:\n",
    "            for j in range(len(i)):\n",
    "                if j+1<len(i) and i[j]>0 and i[j+1]>0:\n",
    "                    d+=min(i[j],i[j+1])\n",
    "        return a*6-2*(b+c+d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        sum_cnt = 0\n",
    "        sum_row_max = 0\n",
    "        sum_col_max = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                if j == 0:\n",
    "                    sum_col_max += grid[i][j]\n",
    "                else:\n",
    "                    sum_col_max += abs(grid[i][j]-grid[i][j-1])\n",
    "                if j == len(grid[i])-1:\n",
    "                    sum_col_max += grid[i][j]\n",
    "\n",
    "                if i == 0:\n",
    "                    sum_row_max += grid[i][j]\n",
    "                else:\n",
    "                    sum_row_max += abs(grid[i][j]-grid[i-1][j])\n",
    "                if i == len(grid)-1:\n",
    "                    sum_row_max += grid[i][j]\n",
    "\n",
    "                if grid[i][j] != 0:\n",
    "                    sum_cnt += 2\n",
    "\n",
    "        return sum_cnt + sum_col_max + sum_row_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        N = len(grid)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "\n",
    "        for r in range(N):\n",
    "            for c in range(N):\n",
    "                if grid[r][c]:\n",
    "                    res += 2\n",
    "                    for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
    "\n",
    "                        if 0 <= nr < N and 0 <= nc < N:\n",
    "                            nval = grid[nr][nc]\n",
    "                        else:\n",
    "                            nval = 0\n",
    "                        \n",
    "                        res += max(grid[r][c] - nval, 0)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\r\n",
    "        ans = 0\r\n",
    "        for i in range(len(grid)):\r\n",
    "            for j in range(len(grid[0])):\r\n",
    "                if grid[i][j]:\r\n",
    "                    ans += grid[i][j] * 4 + 2\r\n",
    "                if i:\r\n",
    "                    ans -= min(grid[i][j], grid[i-1][j]) * 2\r\n",
    "                if j:\r\n",
    "                    ans -= min(grid[i][j], grid[i][j-1]) * 2\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        sum_cnt = 0\n",
    "        sum_row_max = 0\n",
    "        sum_col_max = 0\n",
    "        col_dat = {}\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                if j == 0:\n",
    "                    sum_col_max += grid[i][j]\n",
    "                else:\n",
    "                    sum_col_max += abs(grid[i][j]-grid[i][j-1])\n",
    "                if j == len(grid[i])-1:\n",
    "                    sum_col_max += grid[i][j]\n",
    "\n",
    "                if i == 0:\n",
    "                    sum_row_max += grid[i][j]\n",
    "                else:\n",
    "                    sum_row_max += abs(grid[i][j]-grid[i-1][j])\n",
    "                if i == len(grid)-1:\n",
    "                    sum_row_max += grid[i][j]\n",
    "\n",
    "                if grid[i][j] != 0:\n",
    "                    sum_cnt += 2\n",
    "\n",
    "        return sum_cnt + sum_col_max + sum_row_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "\n",
    "        visit = [[0] * n for _ in range(n)]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    ans += grid[i][j] * 4 + 2\n",
    "\n",
    "                for a, b in [(-1,0),(1,0),(0,1),(0,-1)]:\n",
    "                    if 0 <= i + a < n and 0 <= j + b < n and visit[i+a][j + b]:\n",
    "                        ans -= 2 * min(grid[i][j], grid[i + a][j + b])\n",
    "\n",
    "                visit[i][j] = 1\n",
    "                print(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        cnt = sum(grid[0]) + sum(grid[-1]) + sum([grid[i][0] for i in range(m)]) + sum([grid[i][-1] for i in range(m)])\n",
    "        for i in range(m):\n",
    "            for j in range(1, n):\n",
    "                cnt += abs(grid[i][j] - grid[i][j-1])\n",
    "        \n",
    "        for j in range(n):\n",
    "            for i in range(1, m):\n",
    "                cnt += abs(grid[i][j] - grid[i-1][j])\n",
    "\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                cnt += int(grid[i][j] > 0) * 2\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        total_cube, stick_surface = 0, 0\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                high = grid[i][j]\n",
    "                total_cube += high\n",
    "                stick_surface += (high-1)*2\n",
    "                if i > 0:\n",
    "                    stick_surface += min(high, grid[i-1][j])\n",
    "                if i < row-1:\n",
    "                    stick_surface += min(high, grid[i+1][j])\n",
    "                if j > 0:\n",
    "                    stick_surface += min(high, grid[i][j-1])\n",
    "                if j < col-1:\n",
    "                    stick_surface += min(high, grid[i][j+1])\n",
    "        return total_cube*6 - stick_surface\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        def b(a,b,c,d,e):\n",
    "            if a==0:return 0\n",
    "            ans=2\n",
    "            la=[b,c,d,e]\n",
    "            for i in la:\n",
    "                if i<a:ans+=a-i\n",
    "            return ans\n",
    "        k=len(grid)\n",
    "        grid=[[0]*k]+grid+[[0]*k]\n",
    "        for i in range(k+2):grid[i]=[0]+grid[i]+[0]\n",
    "        for i in range(1,k+1):\n",
    "            for j in range(1,k+1):\n",
    "                ans+=b(grid[i][j],grid[i+1][j],grid[i-1][j],grid[i][j+1],grid[i][j-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        x=sum([4*v+2 if v else 0 for row in grid for v in row])\n",
    "        y=sum([2*min(grid[i][j],grid[i-1][j]) for i in range(1,n) for j in range(0,n)])\n",
    "        z=sum([2*min(grid[i][j],grid[i][j-1]) for j in range(1,n) for i in range(0,n)])\n",
    "        return x-y-z\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        def neighbour(r, c):\n",
    "            sub_ngb = 0\n",
    "            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):\n",
    "                if 0 <= nr < rows and 0 <= nc < cols:\n",
    "                    sub_ngb += min(grid[r][c], grid[nr][nc])\n",
    "            return sub_ngb\n",
    "        ans=0\n",
    "        rows = cols = len(grid)\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                if grid[r][c] != 0:\n",
    "                    # 不考虑贴在一起的表面积 = 4 * 高度(grid[r][c]) + 2\n",
    "                    # 表面积 = 不考虑贴在一起的表面积 - 贴在一起的表面积\n",
    "                    ans += 4 * grid[r][c] + 2 - neighbour(r, c)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        ans=n*n*2\n",
    "        ans+=sum(grid[0])+sum(grid[-1])\n",
    "        for j in range(n):\n",
    "            ans+=grid[j][0]\n",
    "            ans+=grid[j][n-1]\n",
    "        temp=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    ans-=2\n",
    "                for x,y in (i+1,j),(i-1,j),(i,j+1),(i,j-1):\n",
    "                    if x>=0 and x<n and y>=0 and y<n:\n",
    "                        temp+=abs(grid[x][y]-grid[i][j])\n",
    "        return ans+(temp//2)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        s=len(grid)\n",
    "        for i in range(s):\n",
    "            for j in range(s):\n",
    "                t=grid[i][j]\n",
    "                #四个边，加上上底和下底\n",
    "                if t:\n",
    "                    ans+= t+t+1\n",
    "                #减去行间重叠部分\n",
    "                if i:\n",
    "                    ans -= min(t,grid[i-1][j])\n",
    "                #减去列间重叠部分\n",
    "                if j:\n",
    "                    ans -= min(t,grid[i][j-1])\n",
    "        return ans<<1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        xy_area = sum([x>0 for row in grid for x in row])\n",
    "\n",
    "        xz_area = self.side_area(grid)\n",
    "        temp_arr = [x for x in zip(*grid)]\n",
    "        yz_area = self.side_area(temp_arr)\n",
    "\n",
    "        return 2*xy_area + xz_area + yz_area\n",
    "        # return xz_area\n",
    "\n",
    "    def side_area(self, grid):\n",
    "        xz_area = 0\n",
    "        for row in range(len(grid)):\n",
    "            star_xz = 0\n",
    "            temp_col = []\n",
    "            for col in range(len(grid[0])):\n",
    "                temp_col.append(abs(grid[row][col] - star_xz))\n",
    "                star_xz = grid[row][col]\n",
    "            temp_col.append(grid[row][col])\n",
    "            xz_area += sum(temp_col)\n",
    "        return xz_area\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\r\n",
    "        res=0\r\n",
    "        # r=[0]*len(grid[0])\r\n",
    "        # l=[0]*len(grid)\r\n",
    "        for i in range(len(grid)):\r\n",
    "            last=0\r\n",
    "            for j in range(len(grid[0])):\r\n",
    "                if grid[i][j]>0:\r\n",
    "                    res+=2\r\n",
    "                res+=abs(grid[i][j]-last)\r\n",
    "                last=grid[i][j]\r\n",
    "            res+=last\r\n",
    "        for j in range(len(grid[0])):\r\n",
    "            last=0\r\n",
    "            for i in range(len(grid)):\r\n",
    "                res+=abs(grid[i][j]-last)\r\n",
    "                last=grid[i][j]\r\n",
    "            res+=last\r\n",
    "                    \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        xy_area = sum([x>0 for row in grid for x in row])\n",
    "\n",
    "        xz_area = self.side_area(grid)\n",
    "        temp_arr = [x for x in zip(*grid)]\n",
    "        yz_area = self.side_area(temp_arr)\n",
    "\n",
    "        return 2*xy_area + xz_area + yz_area\n",
    "        # return xz_area\n",
    "\n",
    "    def side_area(self, grid):\n",
    "        xz_area = 0\n",
    "        for row in range(len(grid)):\n",
    "            star_xz = 0\n",
    "            temp_col = []\n",
    "            for col in range(len(grid[0])):\n",
    "                temp_col.append(abs(grid[row][col] - star_xz))\n",
    "                star_xz = grid[row][col]\n",
    "            temp_col.append(grid[row][col])\n",
    "            xz_area += sum(temp_col)\n",
    "        return xz_area\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] > 0:\n",
    "                    ans += grid[i][j] * 4 + 2\n",
    "                if i > 0:\n",
    "                    ans -= 2*min(grid[i][j],grid[i-1][j])\n",
    "                if j > 0:\n",
    "                    ans -= 2*min(grid[i][j],grid[i][j-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0:\n",
    "                    ans += grid[i][j]*4+2\n",
    "                if i != 0:\n",
    "                    ans -= 2*min(grid[i][j],grid[i-1][j])\n",
    "                if j != 0:\n",
    "                    ans -= 2*min(grid[i][j],grid[i][j-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        N = len(grid)\n",
    "\n",
    "        ans = 0\n",
    "        for r in range(N):\n",
    "            for c in range(N):\n",
    "                if grid[r][c]:\n",
    "                    ans += 2\n",
    "                    for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
    "                        if 0 <= nr < N and 0 <= nc < N:\n",
    "                            nval = grid[nr][nc]\n",
    "                        else:\n",
    "                            nval = 0\n",
    "\n",
    "                        ans += max(grid[r][c] - nval, 0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    if grid[i][j] == 1:\n",
    "                        t = 6\n",
    "                    elif grid[i][j] == 2:\n",
    "                        t = 10\n",
    "                    else:\n",
    "                        t = (grid[i][j]-2)*4 + 10\n",
    "                else:\n",
    "                    continue\n",
    "                if i - 1 >= 0 :\n",
    "                    t -= min(grid[i][j],grid[i-1][j])\n",
    "                if i+1 < n:\n",
    "                    t -= min(grid[i][j],grid[i+1][j])\n",
    "                if j-1 >= 0:\n",
    "                    t -= min(grid[i][j],grid[i][j-1])\n",
    "                if j + 1 < m:\n",
    "                    t -= min(grid[i][j],grid[i][j+1])\n",
    "                ret += t\n",
    "                print(ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        N = len(grid)\n",
    "\n",
    "        ans = 0\n",
    "        for r in range(N):\n",
    "            for c in range(N):\n",
    "                if grid[r][c]:\n",
    "                    ans += 2\n",
    "                    for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):\n",
    "                        if 0 <= nr < N and 0 <= nc < N:\n",
    "                            nval = grid[nr][nc]\n",
    "                        else:\n",
    "                            nval = 0\n",
    "\n",
    "                        ans += max(grid[r][c] - nval, 0)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def surfaceArea(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if n == 1:\n",
    "            return 4 * grid[0][0] + 2\n",
    "        else:\n",
    "            result = 0\n",
    "            #上下表面积\n",
    "            for i in range(len(grid)):\n",
    "                for j in range(len(grid[0])):\n",
    "                    if grid[i][j] != 0:\n",
    "                        result = result + 2\n",
    "            for i in range(len(grid)):\n",
    "                now_height_1 = 0\n",
    "                for j in range(len(grid[0])):\n",
    "                    if grid[i][j] >= now_height_1:\n",
    "                        result = result + grid[i][j] - now_height_1\n",
    "                        now_height_1 = grid[i][j]\n",
    "                    elif grid[i][j - 1] > grid[i][j]:\n",
    "                        now_height_1 = grid[i][j]\n",
    "                now_height_2 = 0\n",
    "                for k in range(len(grid[0]) - 1,-1,-1):\n",
    "                    if grid[i][k] >= now_height_2:\n",
    "                        result = result + grid[i][k] - now_height_2\n",
    "                        now_height_2 = grid[i][k]\n",
    "                    elif grid[i][k + 1] > grid[i][k]:\n",
    "                        now_height_2 = grid[i][k]\n",
    "            for j in range(len(grid[0])):\n",
    "                now_height_3 = 0\n",
    "                for i in range(len(grid)):\n",
    "                    if grid[i][j] >= now_height_3:\n",
    "                        result = result + grid[i][j] - now_height_3\n",
    "                        now_height_3 = grid[i][j]\n",
    "                    elif grid[i - 1][j] > grid[i][j]:\n",
    "                        now_height_3 = grid[i][j]\n",
    "                now_height_4 = 0\n",
    "                for k in range(len(grid) - 1,-1,-1):\n",
    "                    if grid[k][j] >= now_height_4:\n",
    "                        result = result + grid[k][j] - now_height_4\n",
    "                        now_height_4 = grid[k][j]\n",
    "                    elif grid[k + 1][j] > grid[k][j]:\n",
    "                        now_height_4 = grid[k][j]\n",
    "            return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
